﻿using System.Collections.Generic;

namespace com.foxmail.wyyuan1991.Assignment.Solver.Dijstra
{
    /// <summary>
    /// RoutePlanner 提供图算法中常用的路径规划功能。
    /// 2005.09.06
    /// </summary>
    public class RoutePlanner
    {
        #region Plan
        //获取权值最小的路径
        public IRoute Plan(IList<INode> nodeList,CostMatrix c, INode sNode, INode eNode)
        {
            PlanCourse planCourse = new PlanCourse(nodeList,c,sNode.ID);

            INode curNode = this.GetMinWeightRudeNode(planCourse, nodeList, sNode.ID);

            #region 计算过程
            while (curNode != null)
            {
                PassedPath curPath = planCourse[curNode.ID];
                foreach (IArc edge in curNode.ArcList)
                {
                    PassedPath targetPath = planCourse[edge.ENode.ID];
                    double tempWeight = curPath.Weight + c[edge];

                    if (tempWeight < targetPath.Weight)
                    {
                        targetPath.Weight = tempWeight;
                        targetPath.PassedIDList.Clear();
                        targetPath.PassedArcList.Clear();
                        for (int i = 0; i < curPath.PassedIDList.Count; i++)
                        {
                            targetPath.PassedIDList.Add(curPath.PassedIDList[i]);
                        }

                        for (int i = 0; i < curPath.PassedArcList.Count; i++)
                        {
                            targetPath.PassedArcList.Add(curPath.PassedArcList[i]);
                        }

                        targetPath.PassedIDList.Add(curNode);
                        targetPath.PassedArcList.Add(edge);
                    }
                }

                //标志为已处理
                planCourse[curNode.ID].BeProcessed = true;
                //获取下一个未处理节点
                curNode = this.GetMinWeightRudeNode(planCourse, nodeList, sNode.ID);
            }
            #endregion

            //表示规划结束
            return this.GetResult(planCourse, eNode);
        }
        #endregion

        #region private method
        #region GetResult
        //从PlanCourse表中取出目标节点的PassedPath，这个PassedPath即是规划结果
        private IRoute GetResult(PlanCourse planCourse, INode desNode)
        {
            PassedPath pPath = planCourse[desNode.ID];

            if (pPath.Weight == double.MaxValue)
            {
                //无可行路径 
                return null;
            }

            //string[] passedNodeIDs = new string[pPath.PassedIDList.Count];
            RoutePlanResult result = new RoutePlanResult();
            result.NodeList = new List<INode>();
            for (int i = 0; i < pPath.PassedIDList.Count; i++)
            {
                result.NodeList.Add(pPath.PassedIDList[i]);
            }
            result.NodeList.Add(desNode);

            result.ArcList = new List<IArc>();
            for (int i = 0; i < pPath.PassedArcList.Count; i++)
            {
                result.ArcList.Add(pPath.PassedArcList[i]);
            }
            result.NodeList.Add(desNode);

            return result;
        }
        #endregion

        #region GetMinWeightRudeNode
        //从PlanCourse取出一个当前累积权值最小，并且没有被处理过的节点
        private INode GetMinWeightRudeNode(PlanCourse planCourse, IList<INode> nodeList, string originID)
        {
            double weight = double.MaxValue;
            INode destNode = null;

            foreach (INode node in nodeList)
            {
                if (node.ID == originID)
                {
                    continue;
                }

                PassedPath pPath = planCourse[node.ID];
                if (pPath.BeProcessed)
                {
                    continue;
                }

                if (pPath.Weight < weight)
                {
                    weight = pPath.Weight;
                    destNode = node;
                }
            }

            return destNode;
        }
        #endregion
        #endregion
    }
}
